package com.LeetCode.Tree;

/**
 * 恢复二叉搜索树
 * 有两个节点被交换了，要恢复回去
 */
public class RecoverTree {

    TreeNode wrongNode1, wrongNode2, preNode;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int tmp = wrongNode1.val;
        wrongNode1.val = wrongNode2.val;
        wrongNode2.val = tmp;
    }
    // 1 4 3 2 5
    private void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        if(preNode != null && preNode.val > root.val){//中序遍历应该是递增的，所以出现这种情况就说明preNode节点跟root节点有问题
            if(wrongNode1 == null) wrongNode1 = preNode;
            wrongNode2 = root;
        }
        preNode = root;
        inorder(root.right);
    }
}
